Real-time location systems (RTLS) can be used to locate and track people and objects. The global positioning system (GPS) provides accuracy in the order of meters. However, GPS does not work indoors, has a high non-line of sight (NLoS) errors, and a long acquisition time, see S. Gezici, “A survey on wireless position estimation,” Wireless Personal Communications,” Special Issue on Towards Global and Seamless Personal Navigation, vol. 44, no. 3, pp. 263-282, February 2008. Therefore, alternative systems are used for indoor localization and tracking.
As shown in FIG. 1A, a RTLS for indoor use is implemented as a network of devices. The RTLS includes a transmit-only target device 130, and time synchronized anchor devices 101-104s to measure time difference of arrival (TDoA) of radio signals. The TDOA system includes multiple anchor devices (Ri) 101-104 with known positions and a position solver 120, see G. Sun, J. Chen, W. Guo, and K. J. Ray Liu, “Signal Processing Techniques in Network Aided Positioning,” IEEE Signal Proc. Magazine, v. 22, n. 4, pp. 12-23, July 2205, D. Kelly and G. Shreve and D. Langford, “Fusing communications and Positioning-Ultrawideband offers exciting possibilities,” Time
Domain Corporation, August 1998, R. Fontana and S. J. Gunderson, “Ultrawideband precision asset location system,” In Proc. IEEE Conf. on Ultrawideband Syst. and Technol. (UWBST), May 2002, pp. 147-150, and R. J. Fontana, “Experimental results from an ultrawideband precision geolocation system,” Multispectral Solutions, Inc., pp. 1-6, May 2000. The reference devices are synchronized by timing signals via a category-5 (CAT-5) twisted pair cable 110. The devices can also synchronize and communicate with the position solver 120 using the same cable 110.
The target device periodically broadcasts a beacon 111. The reference devices record and forward the time of arrival of the beacons 111 to the position solver 120. The position solver 120 typically uses a non-linear optimization procedure to estimate the location of the target device 130. In a practical application, thousands of targets can be used because the signaling traffic volume requirements are quite low. However, a high cost of installation and calibration impede large-scale deployment.
FIG. 1B shows a two-way time-of-arrival (TW-ToA) RTLS 140 with better accuracy than the TDoA system 100 of FIG. 1A. The TW-ToA 140 does not require synchronization as the TDoA system above, see J-Y. Lee and R. A. Scholtz, “Ranging in a dense multipath environment using an UWB radio link,” IEEE Journal on Selected Areas in Communications, vol. 20, no. 9, pp. 1677-1683, December 2002, and Z. Sahinoglu, S. Gezici, “Ranging in the IEEE 802.15.4a Standard,” In Proc. IEEE Wireless and Microwave Tech. Conf. (WAMICON), Florida, pp. 1-5, May 2006.
In the TW-TOA based RTLS 140, the target device 130 unicasts range request messages 141-144 to reference devices 101-104. In response to receiving the range request messages, the reference devices transmit range reply message 151-154. Thus, the target receives multiple round-trip time measurements. Each round-trip time specifies a circle of possible positions. The intersection of the circles corresponds to the position of the target. Position solving can be done at the target 130 or at any of the reference devices.
FIG. 1C shows an alternative TW-TOA based RTLS system. Here, the signaling is initiated by transmitting range request messages 161-164 from reference devices 101-104 to the target 130. In response to receiving the requests, the target 130 broadcasts range reply messages 171-174. Then, the reference devices relay timing data (181-184) to the position solver 120. The TW-TOA systems have higher traffic volume requirement, and energy consumption is increased. This can be a serious problem in battery-operated positioning devices.
FIG. 1D shows a prior art mono-static radar system with bi-static receivers to determine the position of the target 130. A mono-static radar signal source R1 101 transmits a radar signal 191. The radar signal 191 reflects at the target 130 and is received at the source R1 101. This provides a round-trip time measurement that specifies a circle. The radar signal 191 and reflected signal 192 are also received by a bi-static receiver R2 102, which determines a time difference of arrival that specifies an ellipse. The intersection of the circle and the ellipse indicates the position of the target. As an advantage, this system does not require the cooperation of the target.
There are many cooperative localization schemes in the literature, but their particular emphasis is to increase the accuracy of initial position estimates either via information sharing among nodes that are being located, see C. Fretzagias, M. Papadopouli, “Cooperative Location-sensing for Wireless Networks,” In Proc. Second IEEE Annual Conf. on Pervasive Computing and Commun. (PERCOM), March 2004, and Y. Shen, H. Wymeersch, and M. Z. Win, “Fundamental Limits of Wideband Cooperative Localization via Fisher Information,” In Proc. IEEE Wireless Coomun. and Networking Conf. (WCNC), March 2007, pp. 3954-3958, or data fusion of multiple received signal strength (RSS), angle-of-arrival (AoA) and ToA measurements at multiple nodes, see C. L. F. Mayorga, F. D. Rosa, and S. A. Wardana, “Cooperative Positioning Techniques for Mobile Localization in 4G Cellular Networks,” In Proc. IEEE Int. Conf. on Pervasive Services, July 2007, pp. 39-44, and T. Hui, W. Shuang, and X. Huaiyao, “Localization using Cooperative AOA Approach,” In Proc. IEEE Int. Conf. on Wireless Commun., Networking and Mobile Computing (WiCOM), September 2007, pp. 2416-2419. A. T. Ihler, J. W. Fisher, R. L. Moses, and A. S. Willsky, “Nonparametric Belief Propagation for Self-localization of Sensor Networks,” IEEE Journal on Selected Areas in Communications, vol. 23, no. 4, pp. 809-819, April 2005, describe a cooperative non-parametric belief propagation algorithm is developed to determine the infrastructure map.
Even though that approach suffers from mobility, it complements the current work, which assumes that the locations of the anchor nodes are known a-priori. Another complementary work, see N. A. Alsindi, K. Pahlavan, B. Alavi, and X. Li, “A Novel Cooperative Localization Algorithm for Indoor Sensor Networks,” In Proc. 17th Annual IEEE Int. Symposium on Personal, Indoor and Mobile Radio Commun. (PIMRC), September 2006, pp. 1-6, describes introduces a distributed method to mitigate propagation of anchor location estimation errors. It is also possible to use the position estimates obtained by means of the current cooperative algorithm to initialize those methods.
Radar systems that having simultaneous mono-static and bi-static modes of operation are described by R. Braff, “Ranging and Processing Mobile Satellite,” IEEE Trans. on Aerospace and Electronic Systems, vol. 24, no. 1, pp. 14-22, January 1988. There, the target is non-cooperative. In other words, the signals reflect back from the target without inducing and turn-around time. In communication systems, turn around time dominates the propagation time. Therefore, target cooperation is needed.
The above described systems either suffer from high energy consumption and low traffic capacity (for TW-TOA), or high deployment and infrastructure cost (for TDOA). Each air transmission and reception consumes energy. Therefore, minimizing transmissions reduces energy consumption of devices. Therefore, there is a need for an RTLS system with higher traffic efficiency than TW-TOA and lower deployment cost than TDOA.